// Copyright (C) 2011 by Christopher Diggins
// Usage is permitted under the terms of the MIT License 1.0. 	

/** \file
	Contains implementation of table functions.
	\see \ref table
*/

/** Computes a hash value from an integer. */
uint table_hash(uint n) {
	n ^= n << 3; n += n >> 5; n ^= n << 4; n += n >> 17; n ^= n << 25; n += n >> 6;
	return n;
}

/** Initializes a table value. */
Val* table_alloc_impl(Val* table, uint n) {
	assert(val_is_table(table));
	obj_array(table) = (Array*)calloc(n, sizeof(Array));
	obj_array(table)->data = (byte*)calloc(n, sizeof(KeyVal));
	table_count(table) = 0;
	table_size(table) = n;
	return table;
}

/** Returns the KeyVal pair with the existing key. If no value
	is found, the KeyVal pair will have a NULL as the value
	and can be used for adding a value. Quadratic probing is 
	used for collision resolution. */
KeyVal* table_find(Val* table, uint key) {	
	uint sz = table_size(table);
	KeyVal* kvs = table_begin(table);
	uint h = table_hash(key);
	uint n = h % sz;
	uint i = 1;
	assert(val_is_table(table));
	while (table_slot_occupied(kvs + n)) {
		if (kvs[n].key == key) break;
		n = (n + i) % sz;
		i = i * 2 + 1; 
	}	
	return kvs + n;
}

/** Increase the size of a hash table, and redistributes existing items. */
void table_grow_impl(VM* vm, Val* table) {
	uint n = table_size(table) * TABLE_GROWTH_FACTOR + 1;

	KeyVal* begin = table_begin(table);
	KeyVal* end = table_end(table);

	// Get the pointer to the old data
	byte* old = obj_array(table)->data;
	assert((void*)begin == (void*)old);

	// Allocate more data.
	table_alloc(table, n << 1);

	// Add the old items to the new table.
	for (; begin != end; ++begin)
		if (table_slot_occupied(begin))
			table_add(table, begin->key, begin->val);

	// Free the old table data 
	free(old);
}

/** Adds a key and value to a table. The value does not have its reference count 
	incremented. However when removed the reference count is removed. Therefore
	oqwnership of the value is transferred to the table via this function. */
void table_add_impl(VM* vm, Val* table, uint key, Val* val) {
	KeyVal* kv = table_find(table, key);
	assert(val_is_table(table));
	assert(table_count(table) < table_size(table));
	assert(val);
	assert(!kv->val);

	table_count(table)++;
	kv->key = key;
	kv->val = val;

	if (table_load(table) >= TABLE_MAX_LOAD)
		table_grow_impl(vm, table);
}
